#include "Graph.hpp"
#include <set>
#include <map>
#include <stack>

template <typename T>
auto createGraph() {
    Graph<T> G(9);
    std::map<uint32_t, vector<std::pair<size_t, T>>> edges;
    edges[1] = { {2, 0}, {5, 0} };
    edges[2] = { {1, 0}, {5, 0}, {4, 0} };
    edges[3] = { {4, 0}, {7, 0} };
    edges[4] = { {2, 0}, {3, 0}, {5, 0}, {6, 0}, {8, 0} };
    edges[5] = { {1, 0}, {2, 0}, {4, 0}, {8, 0} };
    edges[6] = { {4, 0}, {7, 0}, {8, 0} };
    edges[7] = { {3, 0}, {6, 0} };
    edges[8] = { {4, 0}, {5, 0}, {6, 0} };
    for (auto& i : edges)
        for (auto& j : i.second)
            G.addEdge(Edge<T>{i.first, j.first, j.second});
    return G;
}

template <typename T>
auto depthFirstSearch(const Graph<T>& G, size_t dest) {
    std::stack<size_t> stack;
    vector<size_t> visitOrder;
    std::set<size_t> visited;
    stack.push(dest); //从给定的dest开始搜索
    while (!stack.empty()) {
        auto currentVertex = stack.top();
        stack.pop();
        if (visited.find(currentVertex) == visited.end()) {
            visited.insert(currentVertex);
            visitOrder.push_back(currentVertex);
            //遍历当前顶点的所有边
            for (const auto& e : G.edgesFromVertex(currentVertex)) {
                //如果边的终点尚未被访问
                if (visited.find(e.dest) == visited.end())
                    //将该终点压入栈中
                    stack.push(e.dest);
            }
        }
    }
    return visitOrder;
}

template <typename T>
void testDFS() {
    auto G = createGraph<T>();
    cout << G << endl;
    cout << "DFS Order of vertices:\n";
    auto DFSVisitOrder = depthFirstSearch<T>(G, 1);
    for (const auto& v : DFSVisitOrder)
        cout << v << " -> ";
    cout << "finish\n";
}

int main(int argc, const char** argv) {
    using T = uint32_t;
    testDFS<T>();
    return 0;
}